package 排序;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/median-of-two-sorted-arrays/
 */
public class _4_寻找两个正序数组的中位数 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l = nums1.length;
        int r = nums2.length;

        int lo1 = 0;
        int lo2 = 0;

        List<Integer> list = new ArrayList<>();

        while (list.size() <= (l + r) / 2) {
            Integer a = null;
            if (lo1 < l) {
                a = nums1[lo1];
            }

            Integer b = null;
            if (lo2 < r) {
                b = nums2[lo2];
            }

            if (a == null) {
                list.add(b);
                lo2++;
                continue;
            }

            if (b == null) {
                list.add(a);
                lo1++;
                continue;
            }

            if (a > b) {
                list.add(b);
                lo2++;
            } else {
                list.add(a);
                lo1++;
            }
        }

        // 这边是元数据长度判断
        if ((l + r) % 2 == 0) {
            int middle = list.size() - 1;
            int a = list.get(middle);
            int b = list.get(middle - 1);

            // 这边除以2.0,计算出来的值就是double类型
            return (a + b) / 2.0;
        }

        //这边向下取整
        return list.get(list.size() - 1) / 1.0;
    }

    // 这种时间复杂度为O(n)，不符合要求
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length + nums2.length];

        for (int i = 0; i < nums1.length; i++) {
            result[i] = nums1[i];
        }

        for (int i = 0; i < nums2.length; i++) {
            result[nums1.length + i] = nums2[i];
        }

        Arrays.sort(result);

        if (result.length % 2 == 0) {
            int middle = result.length / 2;
            int a = result[middle];
            int b = result[middle - 1];

            return (a + b) / 2;
        }
        Double middle = Math.floor(result.length / 2);
        return result[middle.intValue()];
    }

}
